package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 朱城委 on 2021-7-17.<br><br>
 *
 * 二进制手表
 */
public class Topic401 {

    public static void main(String[] args) {
        Topic401 instance = new Topic401();

        System.out.println(instance.readBinaryWatch(0));
        System.out.println(instance.readBinaryWatch(1));
        System.out.println(instance.readBinaryWatch(2));
        System.out.println(instance.readBinaryWatch(3));
        System.out.println(instance.readBinaryWatch(8));
        System.out.println(instance.readBinaryWatch(9));
        System.out.println(instance.readBinaryWatch(10));
    }

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        readBinaryWatch(turnedOn, 0, new int[10], result);
        return result;
    }

    private void readBinaryWatch(int turnedOn, int index, int[] mark, List<String> result) {
        if(turnedOn == 0) {
            int hour = mark[0] + mark[1] * 2 + mark[2] * 4 + mark[3] * 8;
            int minute = mark[4] + mark[5] * 2 + mark[6] * 4 + mark[7] * 8 + mark[8] * 16 + mark[9] * 32;

            if(hour < 12 && minute < 60) {
                StringBuilder builder = new StringBuilder();
                builder.append(hour).append(":");
                if(minute < 10) {
                    builder.append(0);
                }
                builder.append(minute);
                result.add(builder.toString());
            }
            return ;
        }

        for(int i = index; i < mark.length; i++) {
            mark[i] = 1;
            readBinaryWatch(turnedOn - 1, i + 1, mark, result);
            mark[i] = 0;
        }
    }

    public List<String> readBinaryWatch2(int turnedOn) {
        List<String> result = new ArrayList<>();

        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 60; j++) {
                if(getDigit(i) + getDigit(j) == turnedOn) {
                    StringBuilder builder = new StringBuilder();
                    builder.append(i).append(":");
                    if(j < 10) {
                        builder.append(0);
                    }
                    builder.append(j);
                    result.add(builder.toString());
                }
            }
        }

        return result;
    }

    private int getDigit(int value) {
        int counter = 0;

        while (value != 0) {
            counter++;
            value = value & (value - 1);
        }

        return counter;
    }
} 
